/*
 Solve the optimal problem - cut rods by dynamic programming.

Problem: Serling Enterprise buys long steel rods and cuts them into shorter rods, then sells. Cut is free. For i = 1,2,..., the price pi in dollars that Serling Enterprises charges for a rod of lenght i inches. 
 -------------------------------------
 length i | 1 2 3 4  5  6  7  8  9 10
 -------------------------------------
 price pi | 1 5 8 9 10 17 17 20 24 30
 -------------------------------------
*/
#include <iostream>

using namespace std;
int minInt = -21483648;


int p[11] = {0,1,5,8,9,10,17,17,20,24,30};

int max(int a,int b)
{
	return ((a>b)?a:b);
}

//==========================================================
// Recursive Method

int rod_cut(int *p, int num)
{
	if(num == 0)
	  return 0;
	int opt=-1000000;
	int i;
	for(i=1;i<=num;i++)
	{
		opt = max(opt, p[i]+rod_cut(p,num-i));
	}

	return opt;
}


//==========================================================
// Top down with memoization

int memoized_cut_rog_aux(int *p, int num, int *memo)
{
	int opt;
	if(memo[num] >= 0)
	  return memo[num];
	if(num==0)
	  opt=0;
	else
	{
		opt=minInt;
		int i;
		for(i=1;i<=num;i++)
		{
			opt = max(opt,p[i]+memoized_cut_rog_aux(p,num-i,memo));
		}
	}

	memo[num] = opt;
	return opt;
}

int memoized_cut_rog(int *p, int num)
{
	int *memo = new int[num+1];
	int i;
	for(i=0;i<=num;i++)
	{
		memo[i] = minInt;
	}
	return memoized_cut_rog_aux(p,num,memo);
}


//==========================================================
// Bottom Up 

int bottom_up_cut_rog(int *p, int num)
{
	int *memo = new int[num+1];		// restore the optimal value for each subproblem.
	int j;
	memo[0] = 0;
	for(j=1;j<=num;j++)
	{
		int opt = minInt;
		int i;
		for(i=1;i<=j;i++)
		{
			opt = max(opt, p[i]+memo[j-i]);
		}
		memo[j] = opt;
	}
	return memo[num];
}

//==========================================================
// Reconstruct the solution

void print_cut_rod_step(int *p, int num, int *step)
{
	while(num>0)
	{
		cout << step[num]<<" ";
		num = num - step[num];
	}
	cout << endl;
}
	
int extended_bottom_up_cut_rog(int *p, int num)
{
	int *memo = new int[num+1];
	int *step = new int[num+1];	// restore the cut point.
	int j;
	memo[0]=0;
	for(j=1;j<=num;j++)
	{
		int opt = minInt;
		int i;
		for(i=1;i<=j;i++)
		{
			if(opt<(p[i]+memo[j-i]))
			{
				opt = p[i]+memo[j-i];
				step[j] = i;
			}
		}
		memo[j]=opt;
	}
	print_cut_rod_step(p,num,step);
	return memo[num];
}

//==========================================================
// Main Function

int main()
{
	//int res = rod_cut(p,4);	// test recursive method.
	//int res = memoized_cut_rog(p,4);	// test top-down with memoization method.
	//int res = bottom_up_cut_rog(p,4);	// test bottom-up method.
	int res = extended_bottom_up_cut_rog(p,7); // test extended bottom up method.
	cout << res << endl;
	
	return 0;
}
